from typing import Any, Optional, List, Callable
from collections import deque

class TreeNode:
    """Base tree node class that can be used for binary tree or N-ary tree."""
    
    def __init__(self, val: Any = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        """Initialize a new tree node.
        
        Args:
            val: Node value
            left: Left child node
            right: Right child node
        """
        self.val = val
        self.left = left 
        self.right = right
        self.children: List['TreeNode'] = []
        
    def __str__(self) -> str:
        """String representation of the node."""
        return f"TreeNode(val={self.val})"
        
    def __repr__(self) -> str:
        """Detailed string representation of the node."""
        if self.children:
            return f"TreeNode(val={self.val}, children={self.children})"
        return f"TreeNode(val={self.val}, left={self.left}, right={self.right})"


class BinaryTreeHelper:
    """Helper class for binary tree operations."""
    
    @staticmethod
    def create_node(val: Any) -> TreeNode:
        """Create a new tree node with given value.
        
        Args:
            val: Value for the new node
            
        Returns:
            A new TreeNode instance
        """
        return TreeNode(val)
        
    @staticmethod
    def is_empty(root: Optional[TreeNode]) -> bool:
        """Check if tree is empty.
        
        Args:
            root: Root node of the tree
            
        Returns:
            True if tree is empty, False otherwise
        """
        return root is None
        
    @staticmethod
    def get_height(root: Optional[TreeNode]) -> int:
        """Get height of the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            Height of the tree (0 for empty tree)
        """
        if not root:
            return 0
        return max(BinaryTreeHelper.get_height(root.left), 
                  BinaryTreeHelper.get_height(root.right)) + 1
                  
    @staticmethod
    def preorder_traversal(root: Optional[TreeNode]) -> List[Any]:
        """Preorder traversal of the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of node values in preorder
        """
        result = []
        
        def preorder(node: Optional[TreeNode]):
            if not node:
                return
            result.append(node.val)
            preorder(node.left)
            preorder(node.right)
            
        preorder(root)
        return result
        
    @staticmethod
    def inorder_traversal(root: Optional[TreeNode]) -> List[Any]:
        """Inorder traversal of the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of node values in inorder
        """
        result = []
        
        def inorder(node: Optional[TreeNode]):
            if not node:
                return
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
            
        inorder(root)
        return result
        
    @staticmethod
    def postorder_traversal(root: Optional[TreeNode]) -> List[Any]:
        """Postorder traversal of the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of node values in postorder
        """
        result = []
        
        def postorder(node: Optional[TreeNode]):
            if not node:
                return
            postorder(node.left)
            postorder(node.right)
            result.append(node.val)
            
        postorder(root)
        return result
        
    @staticmethod
    def level_order_traversal(root: Optional[TreeNode]) -> List[List[Any]]:
        """Level order traversal of the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of lists containing node values at each level
        """
        if not root:
            return []
            
        result = []
        queue = deque([root])
        
        while queue:
            level = []
            level_size = len(queue)
            
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                    
            result.append(level)
            
        return result
        
    @staticmethod
    def find_node(root: Optional[TreeNode], target: Any) -> Optional[TreeNode]:
        """Find node with target value in the tree.
        
        Args:
            root: Root node of the tree
            target: Target value to find
            
        Returns:
            Node with target value if found, None otherwise
        """
        if not root:
            return None
            
        if root.val == target:
            return root
            
        left = BinaryTreeHelper.find_node(root.left, target)
        if left:
            return left
            
        return BinaryTreeHelper.find_node(root.right, target)
        
    @staticmethod
    def insert_left(parent: TreeNode, val: Any) -> TreeNode:
        """Insert a new node as left child.
        
        Args:
            parent: Parent node
            val: Value for new node
            
        Returns:
            Newly created node
        """
        parent.left = TreeNode(val)
        return parent.left
        
    @staticmethod
    def insert_right(parent: TreeNode, val: Any) -> TreeNode:
        """Insert a new node as right child.
        
        Args:
            parent: Parent node
            val: Value for new node
            
        Returns:
            Newly created node
        """
        parent.right = TreeNode(val)
        return parent.right
        
    @staticmethod
    def is_leaf(node: TreeNode) -> bool:
        """Check if node is a leaf node.
        
        Args:
            node: Node to check
            
        Returns:
            True if node is a leaf, False otherwise
        """
        return not node.left and not node.right
        
    @staticmethod
    def get_leaves(root: Optional[TreeNode]) -> List[TreeNode]:
        """Get all leaf nodes in the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of all leaf nodes
        """
        leaves = []
        
        def dfs(node: Optional[TreeNode]):
            if not node:
                return
            if BinaryTreeHelper.is_leaf(node):
                leaves.append(node)
            dfs(node.left)
            dfs(node.right)
            
        dfs(root)
        return leaves
        
    @staticmethod
    def print_tree(root: Optional[TreeNode], level: int = 0, prefix: str = "Root: "):
        """Print tree structure.
        
        Args:
            root: Root node of the tree
            level: Current level in tree
            prefix: Prefix string for current node
        """
        if not root:
            return
            
        indent = "  " * level
        print(f"{indent}{prefix}{root.val}")
        
        if root.left:
            BinaryTreeHelper.print_tree(root.left, level + 1, "L--- ")
        if root.right:
            BinaryTreeHelper.print_tree(root.right, level + 1, "R--- ") 
        
    @staticmethod
    def serialize(root: Optional[TreeNode]) -> str:
        """Serialize binary tree to string.
        
        Args:
            root: Root node of the tree
            
        Returns:
            String representation of the tree
        """
        if not root:
            return "null"
            
        queue = deque([root])
        result = []
        
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")
                
        # Remove trailing nulls
        while result and result[-1] == "null":
            result.pop()
            
        return ",".join(result)
        
    @staticmethod
    def deserialize(data: str) -> Optional[TreeNode]:
        """Deserialize string to binary tree.
        
        Args:
            data: String representation of the tree
            
        Returns:
            Root node of the tree
        """
        if not data or data == "null":
            return None
            
        values = data.split(",")
        root = TreeNode(int(values[0]))
        queue = deque([root])
        i = 1
        
        while queue and i < len(values):
            node = queue.popleft()
            
            # Left child
            if i < len(values) and values[i] != "null":
                node.left = TreeNode(int(values[i]))
                queue.append(node.left)
            i += 1
            
            # Right child
            if i < len(values) and values[i] != "null":
                node.right = TreeNode(int(values[i]))
                queue.append(node.right)
            i += 1
            
        return root
        
    @staticmethod
    def get_lca(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
        """Find lowest common ancestor of two nodes.
        
        Args:
            root: Root node of the tree
            p: First node
            q: Second node
            
        Returns:
            Lowest common ancestor node
        """
        if not root or root == p or root == q:
            return root
            
        left = BinaryTreeHelper.get_lca(root.left, p, q)
        right = BinaryTreeHelper.get_lca(root.right, p, q)
        
        if left and right:
            return root
        return left if left else right
        
    @staticmethod
    def find_path(root: Optional[TreeNode], target: Any) -> List[TreeNode]:
        """Find path from root to target node.
        
        Args:
            root: Root node of the tree
            target: Target value to find
            
        Returns:
            List of nodes in path from root to target
        """
        if not root:
            return []
            
        path = []
        
        def dfs(node: Optional[TreeNode]) -> bool:
            if not node:
                return False
                
            path.append(node)
            
            if node.val == target:
                return True
                
            if dfs(node.left) or dfs(node.right):
                return True
                
            path.pop()
            return False
            
        dfs(root)
        return path
        
    @staticmethod
    def get_all_paths(root: Optional[TreeNode]) -> List[List[Any]]:
        """Get all root-to-leaf paths in the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of paths (each path is a list of values)
        """
        if not root:
            return []
            
        paths = []
        
        def dfs(node: TreeNode, current_path: List[Any]):
            current_path.append(node.val)
            
            if not node.left and not node.right:
                paths.append(current_path[:])
            
            if node.left:
                dfs(node.left, current_path)
            if node.right:
                dfs(node.right, current_path)
                
            current_path.pop()
            
        dfs(root, [])
        return paths
        
    @staticmethod
    def has_path_sum(root: Optional[TreeNode], target_sum: int) -> bool:
        """Check if there exists a root-to-leaf path with given sum.
        
        Args:
            root: Root node of the tree
            target_sum: Target path sum
            
        Returns:
            True if such path exists, False otherwise
        """
        if not root:
            return False
            
        if not root.left and not root.right:
            return root.val == target_sum
            
        target_sum -= root.val
        return (BinaryTreeHelper.has_path_sum(root.left, target_sum) or
                BinaryTreeHelper.has_path_sum(root.right, target_sum))
                
    @staticmethod
    def is_symmetric(root: Optional[TreeNode]) -> bool:
        """Check if tree is symmetric around its center.
        
        Args:
            root: Root node of the tree
            
        Returns:
            True if tree is symmetric, False otherwise
        """
        def is_mirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            if not left and not right:
                return True
            if not left or not right:
                return False
                
            return (left.val == right.val and
                    is_mirror(left.left, right.right) and
                    is_mirror(left.right, right.left))
                    
        return not root or is_mirror(root.left, root.right)
        
    @staticmethod
    def clone_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
        """Create a deep copy of the tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            Root node of the cloned tree
        """
        if not root:
            return None
            
        new_root = TreeNode(root.val)
        new_root.left = BinaryTreeHelper.clone_tree(root.left)
        new_root.right = BinaryTreeHelper.clone_tree(root.right)
        
        return new_root
        
    @staticmethod
    def merge_trees(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> Optional[TreeNode]:
        """Merge two binary trees.
        
        The merge rule is that if two nodes overlap,
        then sum node values up as the new value of the merged node.
        
        Args:
            t1: Root of first tree
            t2: Root of second tree
            
        Returns:
            Root of merged tree
        """
        if not t1:
            return t2
        if not t2:
            return t1
            
        merged = TreeNode(t1.val + t2.val)
        merged.left = BinaryTreeHelper.merge_trees(t1.left, t2.left)
        merged.right = BinaryTreeHelper.merge_trees(t1.right, t2.right)
        
        return merged
        
    @staticmethod
    def get_diameter(root: Optional[TreeNode]) -> int:
        """Get diameter of the tree.
        
        The diameter is the length of the longest path between any two nodes.
        
        Args:
            root: Root node of the tree
            
        Returns:
            Diameter of the tree
        """
        diameter = 0
        
        def get_height(node: Optional[TreeNode]) -> int:
            nonlocal diameter
            
            if not node:
                return 0
                
            left_height = get_height(node.left)
            right_height = get_height(node.right)
            
            # Update diameter if path through this node is longer
            diameter = max(diameter, left_height + right_height)
            
            return max(left_height, right_height) + 1
            
        get_height(root)
        return diameter


class NaryTreeNode:
    """Node class for N-ary tree."""
    
    def __init__(self, val: Any = 0, children: Optional[List['NaryTreeNode']] = None):
        """Initialize a new N-ary tree node.
        
        Args:
            val: Node value
            children: List of child nodes
        """
        self.val = val
        self.children = children if children else []
        
    def __str__(self) -> str:
        """String representation of the node."""
        return f"NaryTreeNode(val={self.val})"
        
    def __repr__(self) -> str:
        """Detailed string representation of the node."""
        return f"NaryTreeNode(val={self.val}, children={self.children})"


class NaryTreeHelper:
    """Helper class for N-ary tree operations."""
    
    @staticmethod
    def create_node(val: Any) -> NaryTreeNode:
        """Create a new N-ary tree node.
        
        Args:
            val: Value for the new node
            
        Returns:
            A new NaryTreeNode instance
        """
        return NaryTreeNode(val)
        
    @staticmethod
    def add_child(parent: NaryTreeNode, child: NaryTreeNode) -> None:
        """Add a child node to parent node.
        
        Args:
            parent: Parent node
            child: Child node to add
        """
        parent.children.append(child)
        
    @staticmethod
    def remove_child(parent: NaryTreeNode, child: NaryTreeNode) -> bool:
        """Remove a child node from parent node.
        
        Args:
            parent: Parent node
            child: Child node to remove
            
        Returns:
            True if child was removed, False if not found
        """
        try:
            parent.children.remove(child)
            return True
        except ValueError:
            return False
            
    @staticmethod
    def get_height(root: Optional[NaryTreeNode]) -> int:
        """Get height of the N-ary tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            Height of the tree
        """
        if not root:
            return 0
            
        if not root.children:
            return 1
            
        return max(NaryTreeHelper.get_height(child) for child in root.children) + 1
        
    @staticmethod
    def preorder_traversal(root: Optional[NaryTreeNode]) -> List[Any]:
        """Preorder traversal of N-ary tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of node values in preorder
        """
        result = []
        
        def preorder(node: Optional[NaryTreeNode]):
            if not node:
                return
                
            result.append(node.val)
            for child in node.children:
                preorder(child)
                
        preorder(root)
        return result
        
    @staticmethod
    def postorder_traversal(root: Optional[NaryTreeNode]) -> List[Any]:
        """Postorder traversal of N-ary tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of node values in postorder
        """
        result = []
        
        def postorder(node: Optional[NaryTreeNode]):
            if not node:
                return
                
            for child in node.children:
                postorder(child)
            result.append(node.val)
                
        postorder(root)
        return result
        
    @staticmethod
    def level_order_traversal(root: Optional[NaryTreeNode]) -> List[List[Any]]:
        """Level order traversal of N-ary tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of lists containing node values at each level
        """
        if not root:
            return []
            
        result = []
        queue = deque([root])
        
        while queue:
            level = []
            level_size = len(queue)
            
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                queue.extend(node.children)
                    
            result.append(level)
            
        return result
        
    @staticmethod
    def find_node(root: Optional[NaryTreeNode], target: Any) -> Optional[NaryTreeNode]:
        """Find node with target value in N-ary tree.
        
        Args:
            root: Root node of the tree
            target: Target value to find
            
        Returns:
            Node with target value if found, None otherwise
        """
        if not root:
            return None
            
        if root.val == target:
            return root
            
        for child in root.children:
            result = NaryTreeHelper.find_node(child, target)
            if result:
                return result
                
        return None
        
    @staticmethod
    def get_all_paths(root: Optional[NaryTreeNode]) -> List[List[Any]]:
        """Get all root-to-leaf paths in N-ary tree.
        
        Args:
            root: Root node of the tree
            
        Returns:
            List of paths (each path is a list of values)
        """
        if not root:
            return []
            
        paths = []
        
        def dfs(node: NaryTreeNode, current_path: List[Any]):
            current_path.append(node.val)
            
            if not node.children:
                paths.append(current_path[:])
            
            for child in node.children:
                dfs(child, current_path)
                
            current_path.pop()
            
        dfs(root, [])
        return paths
        
    @staticmethod
    def serialize(root: Optional[NaryTreeNode]) -> str:
        """Serialize N-ary tree to string.
        
        Format: val[child1,child2,...][child21,child22,...]...
        
        Args:
            root: Root node of the tree
            
        Returns:
            String representation of the tree
        """
        if not root:
            return "null"
            
        def serialize_node(node: NaryTreeNode) -> str:
            result = str(node.val)
            
            for child in node.children:
                result += "[" + serialize_node(child) + "]"
                
            return result
            
        return serialize_node(root)
        
    @staticmethod
    def deserialize(data: str) -> Optional[NaryTreeNode]:
        """Deserialize string to N-ary tree.
        
        Args:
            data: String representation of the tree
            
        Returns:
            Root node of the tree
        """
        if data == "null":
            return None
            
        def find_closing_bracket(s: str, start: int) -> int:
            count = 1
            i = start + 1
            while i < len(s):
                if s[i] == "[":
                    count += 1
                elif s[i] == "]":
                    count -= 1
                if count == 0:
                    return i
                i += 1
            return -1
            
        def deserialize_node(s: str) -> NaryTreeNode:
            # Find value
            i = 0
            while i < len(s) and s[i] != "[":
                i += 1
            val = int(s[:i])
            node = NaryTreeNode(val)
            
            # Find children
            while i < len(s):
                if s[i] == "[":
                    end = find_closing_bracket(s, i)
                    child = deserialize_node(s[i+1:end])
                    node.children.append(child)
                    i = end + 1
                else:
                    i += 1
                    
            return node
            
        return deserialize_node(data)
        
    @staticmethod
    def print_tree(root: Optional[NaryTreeNode], level: int = 0, prefix: str = "Root: "):
        """Print N-ary tree structure.
        
        Args:
            root: Root node of the tree
            level: Current level in tree
            prefix: Prefix string for current node
        """
        if not root:
            return
            
        indent = "  " * level
        print(f"{indent}{prefix}{root.val}")
        
        for i, child in enumerate(root.children):
            NaryTreeHelper.print_tree(child, level + 1, f"C{i+1}--- ")


class BSTHelper:
    """Helper class for Binary Search Tree operations."""
    
    @staticmethod
    def insert(root: Optional[TreeNode], val: Any) -> TreeNode:
        """Insert a value into BST.
        
        Args:
            root: Root node of the BST
            val: Value to insert
            
        Returns:
            Root node of the updated BST
        """
        if not root:
            return TreeNode(val)
            
        if val < root.val:
            root.left = BSTHelper.insert(root.left, val)
        elif val > root.val:
            root.right = BSTHelper.insert(root.right, val)
            
        return root
        
    @staticmethod
    def delete(root: Optional[TreeNode], val: Any) -> Optional[TreeNode]:
        """Delete a value from BST.
        
        Args:
            root: Root node of the BST
            val: Value to delete
            
        Returns:
            Root node of the updated BST
        """
        if not root:
            return None
            
        if val < root.val:
            root.left = BSTHelper.delete(root.left, val)
        elif val > root.val:
            root.right = BSTHelper.delete(root.right, val)
        else:
            # Node with only one child or no child
            if not root.left:
                return root.right
            elif not root.right:
                return root.left
                
            # Node with two children
            # Get inorder successor (smallest in right subtree)
            temp = BSTHelper.get_min_node(root.right)
            root.val = temp.val
            root.right = BSTHelper.delete(root.right, temp.val)
            
        return root
        
    @staticmethod
    def search(root: Optional[TreeNode], val: Any) -> Optional[TreeNode]:
        """Search for a value in BST.
        
        Args:
            root: Root node of the BST
            val: Value to search for
            
        Returns:
            Node containing the value if found, None otherwise
        """
        if not root or root.val == val:
            return root
            
        if val < root.val:
            return BSTHelper.search(root.left, val)
        return BSTHelper.search(root.right, val)
        
    @staticmethod
    def get_min_node(root: TreeNode) -> TreeNode:
        """Get node with minimum value in BST.
        
        Args:
            root: Root node of the BST
            
        Returns:
            Node with minimum value
        """
        current = root
        while current.left:
            current = current.left
        return current
        
    @staticmethod
    def get_max_node(root: TreeNode) -> TreeNode:
        """Get node with maximum value in BST.
        
        Args:
            root: Root node of the BST
            
        Returns:
            Node with maximum value
        """
        current = root
        while current.right:
            current = current.right
        return current
        
    @staticmethod
    def get_successor(root: TreeNode, val: Any) -> Optional[TreeNode]:
        """Find inorder successor of a value in BST.
        
        Args:
            root: Root node of the BST
            val: Value to find successor for
            
        Returns:
            Successor node if exists, None otherwise
        """
        # Find the node first
        current = BSTHelper.search(root, val)
        if not current:
            return None
            
        # If right subtree exists, return minimum in right subtree
        if current.right:
            return BSTHelper.get_min_node(current.right)
            
        # Otherwise, find the lowest ancestor where given node is in left subtree
        successor = None
        ancestor = root
        
        while ancestor != current:
            if current.val < ancestor.val:
                successor = ancestor
                ancestor = ancestor.left
            else:
                ancestor = ancestor.right
                
        return successor
        
    @staticmethod
    def get_predecessor(root: TreeNode, val: Any) -> Optional[TreeNode]:
        """Find inorder predecessor of a value in BST.
        
        Args:
            root: Root node of the BST
            val: Value to find predecessor for
            
        Returns:
            Predecessor node if exists, None otherwise
        """
        # Find the node first
        current = BSTHelper.search(root, val)
        if not current:
            return None
            
        # If left subtree exists, return maximum in left subtree
        if current.left:
            return BSTHelper.get_max_node(current.left)
            
        # Otherwise, find the lowest ancestor where given node is in right subtree
        predecessor = None
        ancestor = root
        
        while ancestor != current:
            if current.val > ancestor.val:
                predecessor = ancestor
                ancestor = ancestor.right
            else:
                ancestor = ancestor.left
                
        return predecessor
        
    @staticmethod
    def is_bst(root: Optional[TreeNode]) -> bool:
        """Check if tree is a valid BST.
        
        Args:
            root: Root node of the tree
            
        Returns:
            True if tree is a valid BST, False otherwise
        """
        def is_bst_util(node: Optional[TreeNode], min_val: Any, max_val: Any) -> bool:
            if not node:
                return True
                
            if node.val <= min_val or node.val >= max_val:
                return False
                
            return (is_bst_util(node.left, min_val, node.val) and
                   is_bst_util(node.right, node.val, max_val))
                   
        return is_bst_util(root, float('-inf'), float('inf'))
        
    @staticmethod
    def get_range(root: Optional[TreeNode], low: Any, high: Any) -> List[Any]:
        """Get all values in BST within given range.
        
        Args:
            root: Root node of the BST
            low: Lower bound (inclusive)
            high: Upper bound (inclusive)
            
        Returns:
            List of values within the range in sorted order
        """
        result = []
        
        def inorder(node: Optional[TreeNode]):
            if not node:
                return
                
            if low < node.val:
                inorder(node.left)
                
            if low <= node.val <= high:
                result.append(node.val)
                
            if node.val < high:
                inorder(node.right)
                
        inorder(root)
        return result
        
    @staticmethod
    def is_balanced(root: Optional[TreeNode]) -> bool:
        """Check if BST is height-balanced.
        
        Args:
            root: Root node of the BST
            
        Returns:
            True if BST is balanced, False otherwise
        """
        def get_height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            return max(get_height(node.left), get_height(node.right)) + 1
            
        if not root:
            return True
            
        left_height = get_height(root.left)
        right_height = get_height(root.right)
        
        return (abs(left_height - right_height) <= 1 and
                BSTHelper.is_balanced(root.left) and
                BSTHelper.is_balanced(root.right))


class TreeHelper:
    """Helper class for general tree operations."""
    
    @staticmethod
    def list_to_tree(data: List[dict], id_field: str = "id", parent_field: str = "parent_id") -> Optional[TreeNode]:
        """Convert a list of dictionaries to a tree structure.
        
        Args:
            data: List of dictionaries containing node data
            id_field: Name of the field containing node ID
            parent_field: Name of the field containing parent ID
            
        Returns:
            Root node of the tree
        """
        if not data:
            return None
            
        # Create nodes dictionary
        nodes = {}
        for item in data:
            node = TreeNode(item)
            node.children = []
            nodes[item[id_field]] = node
            
        # Build tree structure
        root = None
        for item in data:
            node = nodes[item[id_field]]
            parent_id = item[parent_field]
            
            if parent_id is None:
                root = node
            else:
                parent = nodes.get(parent_id)
                if parent:
                    parent.children.append(node)
                    
        return root
        
    @staticmethod
    def tree_to_list(root: Optional[TreeNode], id_field: str = "id", parent_field: str = "parent_id") -> List[dict]:
        """Convert a tree structure to a list of dictionaries.
        
        Args:
            root: Root node of the tree
            id_field: Name of the field containing node ID
            parent_field: Name of the field containing parent ID
            
        Returns:
            List of dictionaries containing node data
        """
        if not root:
            return []
            
        result = []
        
        def traverse(node: TreeNode, parent_id: Any = None):
            # Get node data
            data = node.val.copy() if isinstance(node.val, dict) else {"value": node.val}
            data[parent_field] = parent_id
            result.append(data)
            
            # Process children
            for child in node.children:
                traverse(child, data[id_field])
                
        traverse(root)
        return result
        
    @staticmethod
    def find_node(root: Optional[TreeNode], predicate: Callable[[TreeNode], bool]) -> Optional[TreeNode]:
        """Find a node in the tree that matches the predicate.
        
        Args:
            root: Root node of the tree
            predicate: Function that takes a node and returns True if it matches
            
        Returns:
            Matching node if found, None otherwise
        """
        if not root:
            return None
            
        if predicate(root):
            return root
            
        for child in root.children:
            result = TreeHelper.find_node(child, predicate)
            if result:
                return result
                
        return None
        
    @staticmethod
    def get_node_path(root: Optional[TreeNode], target: TreeNode) -> List[TreeNode]:
        """Get path from root to target node.
        
        Args:
            root: Root node of the tree
            target: Target node to find path to
            
        Returns:
            List of nodes in path from root to target
        """
        if not root:
            return []
            
        path = []
        
        def find_path(node: TreeNode) -> bool:
            path.append(node)
            
            if node == target:
                return True
                
            for child in node.children:
                if find_path(child):
                    return True
                    
            path.pop()
            return False
            
        find_path(root)
        return path
        
    @staticmethod
    def traverse(root: Optional[TreeNode], callback: Callable[[TreeNode], None]) -> None:
        """Traverse the tree and call callback for each node.
        
        Args:
            root: Root node of the tree
            callback: Function to call for each node
        """
        if not root:
            return
            
        callback(root)
        for child in root.children:
            TreeHelper.traverse(child, callback)
            
    @staticmethod
    def to_json(root: Optional[TreeNode]) -> str:
        """Convert tree to JSON string.
        
        Args:
            root: Root node of the tree
            
        Returns:
            JSON string representation of the tree
        """
        if not root:
            return "null"
            
        def node_to_dict(node: TreeNode) -> dict:
            result = {
                "value": node.val,
                "children": [node_to_dict(child) for child in node.children]
            }
            return result
            
        import json
        return json.dumps(node_to_dict(root))
        
    @staticmethod
    def from_json(json_str: str) -> Optional[TreeNode]:
        """Create tree from JSON string.
        
        Args:
            json_str: JSON string representation of the tree
            
        Returns:
            Root node of the tree
        """
        if json_str == "null":
            return None
            
        import json
        data = json.loads(json_str)
        
        def dict_to_node(d: dict) -> TreeNode:
            node = TreeNode(d["value"])
            node.children = [dict_to_node(child) for child in d["children"]]
            return node
            
        return dict_to_node(data)